UVa/216 - Getting in line/216.3.cpp

   1 /*
   2   Wrong answer
   3  */
   4 #include <cmath>
   5 #include <iostream>
   6 #include <algorithm>
   7 #include <vector>
   8 #include <queue>
   9
  10 #define popcount(x) __builtin_popcount(x)
  11
  12 using namespace std;
  13
  14 struct state{
  15   int i, v;
  16   double w;
  17   vector<int> o;
  18   state(int I, int V, double W, vector<int> O) : i(I), v(V), w(W), o(O) {}
  19   bool operator < (const state &that) const {
  20     return w > that.w;
  21   }
  22 };
  23
  24
  25 int main(){
  26   int n, N=1;
  27   while (cin >> n && n){
  28
  29     vector<pair<int, int> > p(n);
  30     for (int i=0; i<n; ++i){
  31       cin >> p[i].first >> p[i].second;
  32     }
  33
  34     double longest = 0.0;
  35     int start;
  36     double g[n][n];
  37     for (int i=0; i<n; ++i){
  38       for (int j=i; j<n; ++j){
  39         g[i][j] = g[j][i] = hypot(p[i].first - p[j].first, p[i].second - p[j].second) + 16.0;
  40         if (g[i][j] > longest){
  41           start = i;
  42           longest = g[i][j]; //Esta suposición da Wrong answer.
  43         }
  44       }
  45     }
  46
  47     double d[1<<n][n];
  48     for (int i=0; i<(1<<n); ++i){
  49       for (int j=0; j<n; ++j){
  50         d[i][j] = 1E100;
  51       }
  52     }
  53
  54     priority_queue<state> q;
  55
  56     d[1<<start][start] = 0;
  57     q.push(state(start, 1<<start, 0.0, vector<int>(1, start))); //Esta suposición da Wrong answer.
  58
  59
  60     while (q.size()){
  61       state top = q.top();
  62       q.pop();
  63
  64       //printf("Saqué de la pila: i = %d, v = %x, w = %lf\n", top.i, top.v, top.w);
  65
  66       if (d[top.v][top.i] < top.w) continue;
  67
  68       if (popcount(top.v) == n){ //Solution
  69         printf("**********************************************************\n");
  70         printf("Network #%d\n", N++);
  71         double t = 0.0;
  72         for (int i=0; i<n-1; ++i){
  73           printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",
  74                  p[top.o[i]].first, p[top.o[i]].second,
  75                  p[top.o[i+1]].first, p[top.o[i+1]].second,
  76                  g[top.o[i]][top.o[i+1]]);
  77           t += g[top.o[i]][top.o[i+1]];
  78         }
  79         printf("Number of feet of cable required is %.2f.\n", t);
  80         break;
  81       }
  82
  83       for (int i=0; i<n; ++i){
  84         //printf("Intetando ir al vecino %d\n", i);
  85         if ((top.v & (1<<i)) == 0){ //Si no había visitado el i
  86           if (top.w + g[top.i][i] < d[top.v | (1<<i)][i]){
  87             d[top.v | (1<<i)][i] = top.w + g[top.i][i];
  88             top.o.push_back(i);
  89             q.push(state(i, top.v | (1<<i), top.w + g[top.i][i], top.o));
  90             top.o.erase(top.o.end() - 1);
  91           }
  92         }
  93       }
  94     }
  95   }
  96   return 0;
  97 }